package com.agile.leetcode.map.ownmap;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author ChenZhangKun
 * @Date 2020/10/13 14:11
 */
public class CzkMap<K,V> implements Map<K,V> {
    // 默认加载因子
    private static final float DEFAULT_LOAD_FACTOR=0.75F;
    // 默认数组长度
    private static  int DEFAULT_MAP_LENGTH=10;
    // 默认数组
    private Entry<K,V>[] table;
    // 长度
    private int length;
    public CzkMap(){
        // 默认长度为10
        this(10);
    }
    public CzkMap(int initSize) {
        this.table = new Entry[DEFAULT_MAP_LENGTH];
    }

    /**
     * map长度
     * @return
     */
    public int size(){
        return length;
    }

    /**
     * 简单的求hash
     * @param k
     * @return
     */
    private int hash(K k){
        return table.length%k.hashCode();
    }

    /**
     * 移除某个key
     * @param k
     * @return
     */
    public V remove(K k){
        // hash
        int hash = hash(k);
        //
        if (table[hash]==null){
            throw new RuntimeException("没有此key");
        }else {
            Entry<K, V> entry = table[hash];
            do {
                if (entry.next.key==k||entry.next.key.equals(k)){
                    V v=entry.next.value;
                    entry.next=entry.next.next;
                    length--;
                    return v;
                }
            }while (entry!=null);
        }
        return null;
    }
    /**
     * 扩容
     * @param newSize
     */
    private void reSize(int newSize){
        Entry[] newEntry=new Entry[newSize];
        DEFAULT_MAP_LENGTH=newSize;
        this.length=0;
        this.reHash(newEntry);
    }

    private void reHash(Entry[] newEntry) {
        // 先将entry保存到集合
        List<Entry<K,V>> list=new ArrayList<>(16);
        for (Entry<K, V> entry : this.table) {
            do {
                list.add(entry);
                entry=entry.next;
            }while (entry!=null);
        }
        // 遍历集合
        if (newEntry.length>0){
            table=newEntry;
        }
        for (Entry<K, V> kvEntry : list) {
            put(kvEntry.getKey(),kvEntry.getValue());
        }
    }

    /**
     * 向map中添加键值对
     * @param k
     * @param v
     * @return
     */
    @Override
    public V put(K k, V v) {
        // 查看是否需要扩容
        if (length>DEFAULT_MAP_LENGTH*DEFAULT_LOAD_FACTOR){
            reSize(2*DEFAULT_MAP_LENGTH);
        }
        // 先求k的hash
        int hash = this.hash(k);
        // 查看有没有值
        if (table[hash]==null){
            table[hash]=new Entry(k,v,null);
            length++;
            return v;
        }else {
            // 遍历链表值查看有没有重复的
            Entry<K, V> entry = table[hash];
            V oldValue;
            do {
                if (entry.getKey()==k||entry.getKey().equals(k)){
                    // 拿到value值
                    oldValue=entry.value;
                    entry.value=v;
                    return oldValue;
                }
                entry=entry.next;
            }while (entry!=null);
            // 如果没有覆盖
            table[hash]=new Entry<>(k,v,table[hash]);
            length++;
            return v;
        }
    }

    @Override
    public V get(K k) {
        // 查看有没有值
        int hash = this.hash(k);
        if (table[hash]==null){
            return null;
        }else {
            // 遍历链表
            Entry<K, V> entry = table[hash];
            do {
                if (entry.key==k||entry.key.equals(k)){
                    V v=entry.value;
                    return v;
                }
                entry=entry.next;
            }while (entry!=null);
        }
        return null;
    }
    class Entry<K,V> implements Map.Entry<K,V>{
        private K key;
        private V value;
         Entry<K,V> next;

        public Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }
    }
}
